package 栈;

import java.util.*;

public class No316去除重复字母 {

    /**
     * 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。
     * 需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
     *
     * 示例 1：
     * 输入：s = "bcabc"
     * 输出："abc"
     * 示例 2：
     * 输入：s = "cbacdcbc"
     * 输出："acdb"
     */

    public String removeDuplicateLetters(String s) {

        /**
         * 前一个字母后面有没有更多的或者更小的,这种思路是错的
         *
         * 正确的思路应该是: 当前元素和栈顶元素比较,如果 1.栈顶元素后序还会出现 2.栈顶元素比当前元素大
         * 那就将栈顶弹出,while到 1,2其中有一个不符合为止,然后将当前元素入栈
         */

        if(s.length()<1){
            return null;
        }

        int[] lettersCount=new int[26];
        boolean[] inStack=new boolean[26];
        char[] arr=s.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            lettersCount[arr[i]-'a']++;
        }

        Deque<Character> stack=new ArrayDeque<>();

        int index=0;
        while (index<arr.length){

            if(inStack[arr[index]-'a']){
                lettersCount[arr[index]-'a']--;
                index++;
                continue;//已经存在,则存在的已经校验过了,所以跳过
            }

            while (!stack.isEmpty()&&stack.peekLast()>=arr[index]&&lettersCount[stack.peekLast()-'a']>0){
                inStack[stack.pollLast()-'a']=false;
            }

            stack.addLast(arr[index]);
            inStack[arr[index]-'a']=true;
            lettersCount[arr[index]-'a']--;
            index++;
        }

        StringBuilder sb=new StringBuilder();
        while (!stack.isEmpty()){
            sb.append(stack.pollFirst());
        }

        return sb.toString();
    }

    public static void main(String[] args) {
        No316去除重复字母 n=new No316去除重复字母();
        String result = n.removeDuplicateLetters("cbacdcbc");
        System.out.println(result);
    }

}
